package com.sam.questionBank;

import java.util.Random;

/**
 *
 * Created by samwang on 2018/4/25.
 */
public class SimpleList {

    public static void main(String[] args) {
        Random random = new Random();
        int n = random.nextInt(100);
        int j = random.nextInt(n);
        ListNode head = new ListNode();
        head.value = 0;
        ListNode node = head;
        for (int i = 1; i < n; i++) {
            node.next = new ListNode();
            node.next.value = i;
            node = node.next;
        }

        System.out.println(n+","+j+","+lastNValue(head, j));
    }
    private static class ListNode {
        int value;
        ListNode next;
    }


    /**
     * 单向链表的倒数第n个值
     * @param node
     * @param n
     * @return
     */
    public static int lastNValue(ListNode node, int n) {
        int index = 0;
        ListNode first = node;
        ListNode second = node;
        while (first.next != null) {
            first = first.next;
            if (index >= n-1) {
                second = second.next;
            }
            index++;
        }
        return second.value;
    }

    /**
     * 反转一个单链表。
     进阶:
     链表可以迭代或递归地反转。你能否两个都实现一遍？
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        ListNode newHead = null;
        ListNode temp;
        while(head!=null){ //循环
            temp = head.next;
            if(newHead == null) {
                newHead = head;
                newHead.next = null;
            }else{
                head.next = newHead;
                newHead = head;
            }
            head = temp;
        }

        return newHead;


    }


    /**
     * 跌代实现 链表反转
     *
     *    if(head == null || head.next == null) {
             return head;
           }
         return reverseListIteration(head,null);
     */
    public ListNode reverseListIteration(ListNode oldHead, ListNode newHead) {
        if(oldHead == null) {
            return newHead;
        }
        ListNode temp = oldHead;
        oldHead = oldHead.next;
        temp.next = newHead;
        newHead = temp;
        return reverseListIteration(oldHead, newHead);
    }



}
